#include<stdio.h>
#include<stdlib.h>

#define MAX 0x0fffffff
/*
 *
 * 这是合并算法的c程序实现
 * 作者：Tmacy
 * 时间：2013-11-26
 *
 */
void merge_sort(int* a,int p,int r);
void merge(int* a,int p,int q,int r);


//a 是数组，p是数组起始下标，q是分支下标，r是数组终点下标
//合并算法
void merge(int* a,int p,int q,int r){

    int n1 = q - p + 1;
    int n2 = r - q;
    //为左数组和右数组分配空间，为max预留空间。
    //max为哨兵，标志数组的结束。
    int* L = (int *)malloc(sizeof(int) * (n1 + 1));
    int* R = (int *)malloc(sizeof(int) * (n2 + 1));

    for(int i = 0;i < n1;i++){
        L[i] = a[p + i];
    }
        
    for(int i = 0;i < n2;i++){
        R[i] = a[q + i + 1];
    }

    L[n1] = MAX;
    R[n2] = MAX;
    //从小到大将左数组和友数组合并。 
    int i,j,k;
    for(i = 0,j = 0,k = p;k <= r;k++){
        if(L[i] <= R[j]){
            a[k] = L[i];
            i++;
        }else{
            a[k] = R[j];
            j++;
        }
    }
   
    free(L);
    L = NULL;
    free(R);
    R = NULL;
    return ; 
}

//合并排序算法
//递归实现

void merge_sort(int* a,int p,int r){
    int q = 0;

    if(p < r){
       q = (p + r) / 2; 
       merge_sort(a,p,q);
       merge_sort(a,q + 1,r);
       merge(a,p,q,r);
    }
    return ;
}

int main(int argc, const char *argv[])
{
    int i;
    int a[10] = {9,8,7,6,2,1,4,10,33,0};

    for(i = 0;i < 10;i++){
        printf(" %d ",a[i]);
    }
    putchar('\n');

    merge_sort(a,0,9);

    for(i = 0;i < 10;i++){
        printf(" %d ",a[i]);
    }
    putchar('\n');

    return 0;
}
